#define  _CRT_SECURE_NO_WARNINGS 1
using namespace std;
#include<iostream>
#include<vector>
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int begin = 0;
        int end = nums.size() - 1;
        while (begin <= end)
        {
            int mid = (begin + end) / 2;
            if (nums[mid] == target)
            {
                return mid;
            }
            else if (nums[mid] < nums[end])
            {
                if (nums[mid] < target && nums[end] >= target)
                {
                    begin = mid + 1;
                }
                else
                {
                    end = mid - 1;
                }
            }
            else//(nums[mid]>nums[end])
            {
                if (nums[mid] > target && target > nums[end])
                {
                    end = mid - 1;
                }
                else
                {
                    begin = mid + 1;
                }
            }
        }
        return -1;
    }
};

int main()
{
    Solution s;
    vector<int> nums = { 4, 5, 6, 7, 0, 1, 2 };
    int a=s.search(nums, 3);
    cout << a<<endl;
    return 0;
}